/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: dings
 * Date: 2024-07-21
 * Time: 22:53
 */
public class Test {
    /**
     * 堆排序：建堆-》堆排序
     * 时间复杂度：O（N*logN）
     * 空间复杂度：O（1）
     * 不稳定
     * @param arr：无序数组
     */
    public void sortHeap(int[] arr) {
        createHeap(arr);
        int end = arr.length-1;
        while (end > 0) {
            swap(arr, 0, end);
            siftDown(arr, 0, end);
            end--;
        }
    }
    /**
     * 向下调整建堆
     * @param arr ：无序数组
     */
    public void createHeap(int[] arr) {
        int parent = (arr.length-1-1)/2;
        for ( ; parent >= 0 ; parent--) {
            siftDown(arr,parent, arr.length);
        }
    }
    /**
     * 向下调整算法
     * @param arr
     * @param parent
     */
    private void siftDown(int[] arr, int parent,int usedSize) {
        int child = parent*2+1;
        while (child < usedSize) {
            if (child+1 < usedSize) {
                if (arr[child+1] > arr[child]) {
                    child += 1;
                }
            }
            if (arr[parent] < arr[child]) {
                swap(arr,parent,child);
                parent = child;
                child = parent*2+1;
            }else {
                break;
            }
        }
    }
}
